package cn.itcast.algorithm;

/**
 * 细胞分裂
 * 初始一个细胞，每一个小时分裂一次，第一个小时2 第二个小时4
 * 同时每两个小时死掉之前的细胞
 * 问：第n个小时有多少细胞
 * create by zhangtian3 on 2019/4/8
 */
public class CellDivision {

    /**
     * 细胞分裂 - 递归算法实现
     * @param n
     * @return
     */
    public static long cellEndNum(int n) {
        if (n <0) {
            return 0 ;
        }

        if (n == 0){
            return 1 ;
        }

        if (n == 1) {
            return 2 ;
        }

        if (n == 2) {
            return 4 ;
        }

        return 2*cellEndNum(n-1) - cellEndNum(n-3) ;
    }

    /**
     * 细胞分裂 - 循环算法实现
     * @param n
     * @return
     */
    public static long cellEndNumCycle(int n) {
        if (n <0) {
            return 0 ;
        }

        long[] arr = new long[n+3] ;
        arr[0] = 1 ;
        arr[1] = 2 ;
        arr[2] = 4 ;

        for(int i = 3; i < n+1; i++){
            arr[i] = 2 * arr[i-1] - arr[i-3] ;
        }

        return arr[n] ;
    }
}
